package year2024.month4;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

public class MaximalRectangle {

    @Test
    void test1() {
        Assertions.assertEquals(6, maximalRectangle(
                new char[][]{
                        {'1', '0', '1', '0', '0'},
                        {'1', '0', '1', '1', '1'},
                        {'1', '1', '1', '1', '1'},
                        {'1', '0', '0', '1', '0'}
                }
        ));
    }

    @Test
    void test2() {
        Assertions.assertEquals(0, maximalRectangle(
                new char[][]{
                        {'0'}
                }
        ));
    }

    @Test
    void test3() {
        Assertions.assertEquals(1, maximalRectangle(
                new char[][]{
                        {'1'}
                }
        ));
    }

    /**
     * 85. 最大矩形
     * 给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
     *
     * @param matrix
     * @return
     */
    public int maximalRectangle(char[][] matrix) {

        int max = 0;

        for (int x = 0; x < matrix.length; x++) {
            for (int y = 0; y < matrix[x].length; y++) {
                if (matrix[x][y] == '1') {
                    max = Math.max(max, search(matrix, x, y));
                }
            }
        }
        return max;
    }

    int search(char[][] matrix, int startX, int startY) {

        if (startX < 0 || startX == matrix.length || startY < 0 || startY == matrix[0].length) {
            // 越界
            return 0;
        }

        int x = startX;
        int y = startY;

        int max=0;

        while (++x < matrix.length) {

        }

        return 0;
    }
}
